﻿// 4走迷宫.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//题目和题解：https://cloud.tencent.com/developer/inventory/3847/article/1558197
//
#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>

#define M 30
#define N 50
//#define M 4
//#define N 6

using namespace std;

struct Point
{
    int x, y;
    string path;
    Point():x(0),y(0){}
    Point(int x,int y):x(x),y(y){}
};

//const Point _left(-1, 0), _up(0, 1), _right(1, 0), _down(0, -1);
//DLRU
vector<vector<int> > ward = {
    vector<int>() = {0, -1},
    vector<int>() = {-1, 0},    //妈的这题好阴啊，要注意迷宫的坐标系建立和up down操作是否和迷宫实际坐标系统一
    vector<int>() = {1, 0},
    vector<int>() = {0, 1}
};

string wardCh = "DLRU";

void bfs(vector<string>& map,vector<string>& visited,string& res)
{
    Point start(0, 0);
    queue<Point> que;
    que.push(start);
    visited[0][0] = '1';
    Point p1;
    while (!que.empty())
    {
        p1 = que.front();
        que.pop();
        if (p1.x==N-1&&p1.y==M-1)   //到达终点
        {
            res = p1.path;
            return;
        }
        for (int i = 0; i < ward.size(); i++)
        {
            int dx = p1.x + ward[i][0];
            int dy = p1.y + ward[i][1];

            if ((dx>=0&&dx<N&&dy>=0&&dy<M)&&(map[dy][dx]=='0'&&visited[dy][dx]=='0'))
            {
                Point p2(dx, dy);
                p2.path =p1.path+wardCh[i];
                que.push(p2);
                visited[dy][dx] = '1';
            }

        }
    }
}



int main()
{
    ifstream infile("text01.txt",ios::in);
    if (!infile)
    {
        cout << "err" << endl;
        return 0;
    }

    vector<string> map(M), visited(M,string());
    int i = 0;
    char temp[N+1];
    while (i<M)
    {
        infile.getline(temp, N+1);
        map[i] = temp;
        visited[i].resize(N,'0');
        i++;
    }
    infile.close();
    string res;
    bfs(map, visited, res);
    cout << res;
    //delete temp;
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
